package main.leetcode.clockin.October;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 844. 比较含退格的字符串
 *
 * <p>给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
 *
 * <p>注意：如果对空文本输入退格字符，文本继续为空。
 *
 * <p>示例 1：<br>
 * 输入：S = "ab#c", T = "ad#c" <br>
 * 输出：true <br>
 * 解释：S 和 T 都会变成 “ac”。
 *
 * <p>示例 2：<br>
 * 输入：S = "ab##", T = "c#d#" <br>
 * 输出：true <br>
 * 解释：S 和 T 都会变成 “”。
 *
 * <p>示例 3： 输入：S = "a##c", T = "#a#c" <br>
 * 输出：true <br>
 * 解释：S 和 T 都会变成 “c”。
 *
 * <p>示例 4： 输入：S = "a#c", T = "b" <br>
 * 输出：false <br>
 * 解释：S 会变成 “c”，但 T 仍然是 “b”。
 *
 * <p>提示：<br>
 * 1 <= S.length <= 200 <br>
 * 1 <= T.length <= 200 <br>
 * S 和 T 只含有小写字母以及字符 '#'。
 *
 * <p>进阶：你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
 */
public class day19 {
    public static void main(String[] args) {
        System.out.println(new day19().backspaceCompare("ab#c", "adc"));
    }

    public boolean backspaceCompare(String S, String T) {
        Deque<Character> s = strToStack(S);
        Deque<Character> t = strToStack(T);
        return compare(s, t);
    }

    private boolean compare(Deque<Character> s, Deque<Character> t) {
        if (s.size() != t.size()) {
            return false;
        }
        while (!s.isEmpty()) {
            if (!s.poll().equals(t.poll())) {
                return false;
            }
        }
        return true;
    }

    private Deque<Character> strToStack(String S) {
        Deque<Character> s = new LinkedList<>();
        for (char c : S.toCharArray()) {
            if (c == '#' && !s.isEmpty()) {
                s.poll();
            } else if (c != '#') {
                s.push(c);
            }
        }
        return s;
    }
}
